import model.ListNode;

public class ReorderLis {
    public void code(ListNode head) {
        if (head == null || head.next == null || head.next.next == null){
            return;
        }

        //寻找中间节点
        ListNode slow = head, fast = head;
        while (fast!= null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        //头插出新的一组
        ListNode newHead = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null;   //分离两个链表
        while (cur != null){
            ListNode next = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;

            cur = next;
        }

        //合并两个链表
        ListNode cur1 = head, cur2 = newHead.next;
        ListNode ret = new ListNode(0);
        ListNode prev = ret;

        while (cur1 != null){
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;

            //合并第二个
            if (cur2 != null){
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }
}
